package com.nowcoder.code.lcof;

import java.util.Arrays;

public class JZ85 {


    public static void main(String[] args) {
        JZ85 jz85 = new JZ85();
        int[] is = new int[]{1, -2, 3, 10, -4, 7, 2, -5};
        System.out.println(Arrays.toString(jz85.FindGreatestSumOfSubArray(is)));
    }


    public int[] FindGreatestSumOfSubArray2(int[] array) {
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < array.length; i++) {
            array[i] = Integer.max(array[i - 1] + array[i], array[i]);
            if (array[i] > max) {
                max = array[i];
            }
        }

        System.out.println(max);
        return null;
    }


    public int[] FindGreatestSumOfSubArray(int[] array) {
        int maxStart = 0;
        int maxEnd = 0;
        int start = 0;
        int max = Integer.MIN_VALUE;
        int lastSum = array[0];
        for (int i = 1; i < array.length; i++) {
            int s = lastSum + array[i];
            if (s < array[i]) {
                start = i;
                lastSum = array[i];
            } else {
                lastSum = s;
            }
            if (lastSum > max) {
                max = lastSum;
                maxStart = start;
                maxEnd = i;
            } else if (lastSum == max) {
                if (-start + i > -maxStart + maxEnd) {

                    maxStart = start;
                    maxEnd = i;
                }
            }

        }
        int[] ris = new int[maxEnd - maxStart + 1];
        for (int i = maxStart; i <= maxEnd; i++) {
            ris[i - maxStart] = array[i];
        }

        return ris;
    }
}
